package experiment2;

import java.util.Random;

public class TSP {
    // 城市数量
    private static final int CITY_NUM = 18;
    // 蚂蚁数量
    private static final int ANT_NUM = 50;
    // 最大迭代次数
    private static final int MAX_GEN = 500;
    // 信息素重要性因子
    private static final double ALPHA = 1.0;
    // 启发函数重要性因子
    private static final double BETA = 2.0;
    // 信息素挥发因子
    private static final double RHO = 0.5;
    // 信息素增量因子
    private static final double Q = 100.0;

    private double[][] distances;  // 城市间距离
    private double[][] pheromones; // 信息素矩阵
    private Ant[] ants;           // 蚂蚁群
    private int[] bestTour;       // 最优路径
    private double bestLength;    // 最优路径长度

    public TSP(double[][] distances) {
        this.distances = distances;
        this.pheromones = new double[CITY_NUM][CITY_NUM];
        this.ants = new Ant[ANT_NUM];
        this.bestTour = new int[CITY_NUM];
        this.bestLength = Double.MAX_VALUE;

        // 初始化信息素矩阵和蚂蚁群
        for (int i = 0; i < CITY_NUM; i++) {
            for (int j = 0; j < CITY_NUM; j++) {
                pheromones[i][j] = 1.0; // 初始信息素为1
            }
        }
        for (int i = 0; i < ANT_NUM; i++) {
            ants[i] = new Ant(CITY_NUM);
        }
    }

    public void solve() {
        for (int gen = 0; gen < MAX_GEN; gen++) {
            // 所有蚂蚁构建路径
            for (Ant ant : ants) {
                ant.init();
                for (int step = 1; step < CITY_NUM; step++) {
                    int nextCity = selectNextCity(ant);
                    ant.visitCity(nextCity, distances[ant.getCurrentCity()][nextCity]);
                }
                ant.calculateTourLength(distances);

                // 更新最优路径
                if (ant.getTourLength() < bestLength) {
                    bestLength = ant.getTourLength();
                    System.arraycopy(ant.getTour(), 0, bestTour, 0, CITY_NUM);
                }
            }

            // 更新信息素
            updatePheromones();

            // 输出当前代的最优路径长度
            System.out.printf("第 %d 次迭代: 当前最短路径长度 = %.2f\n", gen + 1, bestLength);
        }

        // 输出最终最优路径和路径长度
        // 输出最终最优路径和路径长度
        System.out.println("最优路径长度: " + bestLength);
        System.out.print("最优路径: ");
        for (int i = 0; i < bestTour.length; i++) {
            System.out.print((bestTour[i] + 1));
            if (i < bestTour.length - 1) {
                System.out.print(" -> "); // 两个城市之间用箭头分隔
            }
        }
        System.out.println(" -> " + (bestTour[0] + 1)); // 回到起点的路径

        System.out.println();
    }

    // 选择下一座城市
    private int selectNextCity(Ant ant) {
        int currentCity = ant.getCurrentCity();
        double[] probabilities = new double[CITY_NUM];
        double total = 0.0;

        // 计算选择概率
        for (int i = 0; i < CITY_NUM; i++) {
            if (!ant.isVisited(i)) {
                probabilities[i] = Math.pow(pheromones[currentCity][i], ALPHA) *
                        Math.pow(1.0 / distances[currentCity][i], BETA);
                total += probabilities[i];
            } else {
                probabilities[i] = 0.0;
            }
        }

        // 轮盘赌选择下一城市
        double rand = new Random().nextDouble() * total;
        double sum = 0.0;
        for (int i = 0; i < CITY_NUM; i++) {
            sum += probabilities[i];
            if (sum >= rand) {
                return i;
            }
        }

        // 如果轮盘赌失败，随机选择一个未访问的城市
        for (int i = 0; i < CITY_NUM; i++) {
            if (!ant.isVisited(i)) {
                return i;
            }
        }

        return -1;
    }

    // 更新信息素
    private void updatePheromones() {
        // 信息素挥发
        for (int i = 0; i < CITY_NUM; i++) {
            for (int j = 0; j < CITY_NUM; j++) {
                pheromones[i][j] *= (1 - RHO);
            }
        }

        // 信息素增加
        for (Ant ant : ants) {
            double contribution = Q / ant.getTourLength();
            int[] tour = ant.getTour();
            for (int i = 0; i < CITY_NUM - 1; i++) {
                pheromones[tour[i]][tour[i + 1]] += contribution;
            }
            pheromones[tour[CITY_NUM - 1]][tour[0]] += contribution;
        }
    }

    // 蚂蚁类
    private static class Ant {
        private int[] tour;           // 当前路径
        private boolean[] visited;    // 是否访问过
        private int currentCity;      // 当前城市
        private double tourLength;    // 路径长度
        private int cityIndex;        // 已访问城市数量

        public Ant(int cityNum) {
            this.tour = new int[cityNum];
            this.visited = new boolean[cityNum];
        }

        public void init() {
            for (int i = 0; i < tour.length; i++) {
                visited[i] = false;
            }
            currentCity = new Random().nextInt(tour.length);
            tour[0] = currentCity;
            visited[currentCity] = true;
            tourLength = 0.0;
            cityIndex = 1;
        }

        public void visitCity(int city, double distance) {
            tour[cityIndex++] = city;
            visited[city] = true;
            tourLength += distance;
            currentCity = city;
        }

        public void calculateTourLength(double[][] distances) {
            tourLength += distances[tour[tour.length - 1]][tour[0]];
        }

        public boolean isVisited(int city) {
            return visited[city];
        }

        public int getCurrentCity() {
            return currentCity;
        }

        public double getTourLength() {
            return tourLength;
        }

        public int[] getTour() {
            return tour;
        }
    }

    public static void main(String[] args) {
        // 城市间距离矩阵
        double[][] distances = {
                {0, 3, 4, 2, 7, 3, 5, 8, 6, 7, 3, 6, 6, 5, 9, 5, 6, 6},
                {3, 0, 4, 6, 3, 5, 6, 3, 5, 6, 4, 5, 4, 3, 7, 5, 6, 6},
                {4, 4, 0, 5, 8, 4, 6, 8, 5, 7, 5, 4, 5, 6, 7, 4, 3, 5},
                {2, 6, 5, 0, 4, 2, 4, 6, 7, 8, 5, 7, 5, 4, 7, 6, 5, 7},
                {7, 3, 8, 4, 0, 5, 4, 3, 5, 6, 7, 6, 5, 7, 8, 5, 4, 3},
                {3, 5, 4, 2, 5, 0, 4, 6, 7, 5, 4, 3, 3, 5, 6, 5, 4, 6},
                {5, 6, 6, 4, 4, 4, 0, 3, 4, 5, 6, 4, 5, 4, 3, 5, 3, 5},
                {8, 3, 8, 6, 3, 6, 3, 0, 3, 4, 5, 7, 8, 6, 7, 8, 5, 4},
                {6, 5, 5, 7, 5, 7, 4, 3, 0, 3, 4, 6, 5, 4, 6, 7, 5, 3},
                {7, 6, 7, 8, 6, 5, 5, 4, 3, 0, 4, 5, 6, 5, 6, 8, 7, 6},
                {3, 4, 5, 5, 7, 4, 6, 5, 4, 4, 0, 3, 4, 5, 7, 4, 3, 5},
                {6, 5, 4, 7, 6, 3, 4, 7, 6, 5, 3, 0, 4, 5, 7, 6, 5, 6},
                {6, 4, 5, 5, 5, 3, 5, 8, 5, 6, 4, 4, 0, 3, 6, 5, 3, 5},
                {5, 3, 6, 4, 7, 5, 4, 6, 4, 5, 5, 5, 3, 0, 6, 4, 3, 5},
                {9, 7, 7, 7, 8, 6, 3, 7, 6, 6, 7, 7, 6, 6, 0, 3, 5, 4},
                {5, 5, 4, 6, 5, 5, 5, 8, 7, 8, 4, 6, 5, 4, 3, 0, 3, 5},
                {6, 6, 3, 5, 4, 4, 3, 5, 5, 7, 3, 5, 3, 3, 5, 3, 0, 4},
                {6, 6, 5, 7, 3, 6, 5, 4, 3, 6, 5, 6, 5, 5, 4, 5, 4, 0}
        };

        TSP tsp = new TSP(distances);
        tsp.solve();
    }
}

